#include <vector>
#include <unordered_set>
#include <string>
#include <sstream>

using namespace std;

// 386. 字典序排数
class Solution1
{
public:
    vector<int> lexicalOrder(int n)
    {
        vector<int> ret(n);
        int num = 1;
        for (int i = 0; i < n; ++i)
        {
            ret[i] = num;
            if (10 * num <= n)
            {
                num *= 10;
            }
            else
            {
                while (num % 10 == 9 || num + 1 > n)
                    num /= 10;
                ++num;
            }
        }
        return ret;
    }
};

// 421. 数组中两个数的最大异或值
class Solution2
{
public:
    int findMaximumXOR(vector<int> &nums)
    {
        int x = 0;
        const int HIGH_BIT = 30;
        for (int k = HIGH_BIT; k >= 0; --k)
        {
            unordered_set<int> seen;
            for (int x : nums)
                seen.insert(x >> k);

            int x_next = 2 * x + 1;
            bool flag = false;

            for (int x : nums)
            {
                if (seen.count(x_next ^ (x >> k)))
                {
                    flag = true;
                    break;
                }
            }

            if (flag)
                x = x_next;
            else
                x = x_next - 1;
        }

        return x;
    }
};

// 440. 字典序的第K小数字
class Solution3
{
private:
    int getSteps(int cur, long n)
    {
        int steps = 0;
        long first = cur, last = cur;
        while (first <= n)
        {
            steps += min(last, n) - first + 1;
            first = 10 * first;
            last = last * 10 + 9;
        }
        return steps;
    }

public:
    int findKthNumber(int n, int k)
    {
        int cur = 1;
        --k;
        while (k > 0)
        {
            int steps = getSteps(cur, n);
            if (steps <= k)
            {
                k -= steps;
                ++cur;
            }
            else
            {
                cur = cur * 10;
                --k;
            }
        }
        return cur;
    }
};

// 648. 单词替换
struct TrieNode
{
    vector<TrieNode*> children;
    string word;

    TrieNode()
        : children(26, nullptr)
        , word("")
    {}
};

class Solution4
{
private:
    void insert(TrieNode* root, const string& word)
    {
        TrieNode* node = root;
        for(char ch : word)
        {
            ch -= 'a';
            if(!node->children[ch]) node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->word = word;
    }

    string findRoot(TrieNode* root, const string& word)
    {
        TrieNode* node = root;
        for(char ch : word)
        {
            ch -= 'a';
            node = node->children[ch];
            if(node && node->word.size() != 0) return node->word;
            else if(node == nullptr) return word;
        }
        return word;
    }

public:
    string replaceWords(vector<string>& dictionary, string sentence) 
    {
        vector<string> words;
        stringstream ss(sentence);
        string str;
        while(ss >> str)
        {
            words.emplace_back(str);
        }

        TrieNode* root = new TrieNode();
        for(auto& word : dictionary) insert(root, word);
        
        for(auto& word : words) word = findRoot(root, word);

        string ret;
        for(int i = 0; i < words.size() - 1; ++i)
        {
            ret += words[i];
            ret += ' ';
        }
        ret += words.back();

        return ret;
    }
};

// 面试题 17.13. 恢复空格
struct Trie
{
    Trie* children[26] = {nullptr};
    bool isEnd = false;
};

class Solution5
{
private:
    void insert(Trie* root, const string& s)
    {
        Trie* node = root;
        for(int i = s.size() - 1; i >= 0; --i)
        {
            int t = s[i] - 'a';
            if(!node->children[t]) node->children[t] = new TrieNode();
            node = node->children[t];
        }
        node->isEnd = true;
    }

public:
    int respace(vector<string>& dictionary, string sentence) 
    {
        int n = sentence.size(), INF = 0x3f3f3f3f;

        Trie* root = new Trie();
        for(auto& word : dictionary) insert(root, word);

        vector<int> dp(n + 1, INF);
        dp[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + 1;
            
            Trie* node = root;
            for(int j = i; j >= 1; --j)
            {
                int t = sentence[j - 1] - 'a';
                if(!node->children[t]) 
                    break;
                else if(node->children[t]->isEnd)
                    dp[i] = min(dp[i], dp[j - 1]);
                
                if(dp[i] == 0) break;
                node = node->children[t];
            }
        }

        return dp[n];
    }
};